215. 数组中的第K个最大元素

发表于 | 分类于
困了困了

215. 数组中的第K个最大元素

30min

拿到题首先想到的当然是直接排序…才怪

但是我们可以优化快速排序来得到结果

解法 1.快速排序

快速排序的思路是从数组中找到一个基准，将数组分为基准，比基准小的部分，比基准大的部分。

而基准本身已经排序完毕，如基准就是第k大元素，则可直接得到结果。

如基准的位置在k左边，则在比基准大的部分中继续找

如基准在k的右边，则在比基准小的部分继续找

需要注意的有三个点

  1. 怎么选择基准 Math.floor(Math.random() * (r - l + 1) + l)
  2. 排序时的区间开闭
  3. 排序后基准记得归位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function swap(a,i,j) {
    [a[i],a[j]] = [a[j],a[i]]
}

var findKthLargest = function(nums, k) {
    var res = null
    function quickSelect(a,l,r) {
        if (l > r) {
            return false
        }
        var piviot = Math.floor(Math.random() * (r - l + 1) + l);
        swap(a,l,piviot)
        let i = l,j = l + 1
        // j 自增
        // [ l ... i] 大于等于基准
        // [i + 1, .... r] 小于基准
        while(j <= r) {
            if (a[j] >= a[l]) {
                swap(a,++i,j)
            }
            j++
        }
        // 基准归位

        swap(a,i,l)
        
        // 此时 i 就 为  i + 1 大的 数
        var _k = i + 1
        if (k === _k) {
            return res = a[i] 
        } else if (_k < k) {
        // 基准小于k,继续查找右边
        quickSelect(a,i+ 1, r)
        } else {
            quickSelect(a,l,i - 1)
        }
    }
    quickSelect(nums,0,nums.length - 1)
    return res
};
解法2. 最大堆

既然是要取第k大的，可以将最大堆最大值取k 次，最后一次就是要的结果

这里难度在我们实现一个最大堆，需要注意的点有

  1. 边界条件，比如shiftUp 时 k最小取到0，shiftDown时的结束条件是没有左子节点。
  2. shiftDown 时需要判断右子节点是否存在
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
function swap(a,i,j) {
    [a[i],a[j]] = [a[j],a[i]]
}
class MaxHeap{
    constructor() {
        this.data = []
    }
    shiftUp(k) {
        while(k >= 0 ) {
            let father  = Math.floor( (k - 1) / 2 )
            if (this.data[k] > this.data[father]) {
                swap(this.data,k,father)
                k = father
            } else {
                break
            }
        }
    }
    shiftDown(k) {
        let len = this.data.length
        while( 2 * k + 1  <= len ) {
            let left = 2 * k + 1
            let right = 2 * k + 2
            let j = k
            if (right <= len && this.data[right] > this.data[k] && this.data[right] > this.data[left]) {
                j = right
            } else if (this.data[left] > this.data[k]) {
                j = left
            } else {
                break
            }
            swap(this.data,j,k)
            k = j
        }
        
    }
    getMax() {
        let ret = this.data[0]
        swap(this.data,0,this.data.length - 1)
        this.data.pop()
        this.shiftDown(0)
        return ret
    }
    insert(a) {
        this.data[this.data.length] = a
        this.shiftUp(this.data.length - 1)
    }
}

var findKthLargest = function(nums, k) {
    var heap = new MaxHeap()
    for(let i = 0 ; i < nums.length ; i ++) {
        heap.insert(nums[i])
    }

    var res = null
    while(k > 0) {
        res = heap.getMax()
        k--
    }
    return res
};